import java.util.Stack;

/**
 * Created with IntelliJ IDEA.
 * Description:
 * Date: 2025-02-03
 * Time: 11:49
 */
class MinStack {

    Stack<Integer> stack;
    Stack<Integer> minStack;
    public MinStack() {
        stack = new Stack<>();
        minStack = new Stack<>();
    }

    public void push(int val) {
        stack.push(val);
        if (minStack.isEmpty()){
            minStack.push(val);
        }else {
            int peekMinVal = minStack.peek();
            if (val <= peekMinVal){
                minStack.push(val);
            }
        }
    }

    public void pop() {
        int val = stack.pop();

        if (val == minStack.peek()){
            minStack.pop();
        }
    }

    public int top() {
        return stack.peek();
    }

    public int getMin() {
        return minStack.peek();
    }

    public boolean isValid(String s) {
        Stack<Character> stack = new Stack<>();
        for(int i = 0;i < s.length();i++){
            char ch = s.charAt(i);

            if(ch == '(' || ch == '{' || ch == '['){
                stack.push(ch);
            }else{
                //右边
                if(stack.isEmpty()){
                    return false;
                }
                char peekCh = stack.peek();
                if((peekCh =='('&&ch == ')') || (ch == '}' && peekCh == '{') || (ch == ']' && peekCh == '[')){
                    stack.pop();
                }else{
                    return false;
                }

            }
        }
        if(!stack.isEmpty()){
            return false;
        }
        return true;
    }

    public boolean IsPopOrder (int[] pushV, int[] popV) {
        Stack<Integer> stack = new Stack<>();

        int j = 0;
        for(int i = 0; i < pushV.length;i++){
            stack.push(pushV[i]);
            while(!stack.isEmpty() && j < popV.length && stack.peek() == popV[j]){
                stack.pop();
                j++;
            }
        }

        return stack.isEmpty();

    }
}